package findMagicIndex;

public class Solution {
    public int findMagicIndex(int[] nums) {
        // 找到索引和下标相同的元素
        return dfs(nums,0,nums.length-1);
    }
    private int dfs (int[] nums,int l,int r) {
        if(l>r) {
            return -1;
        }
        int mid = (l+r)/2;
        int leftAns = dfs(nums,l,mid-1);
        if(leftAns!=-1) {
            return leftAns;
        }else if(mid == nums[mid]){
            return mid;
        }
        return dfs(nums,mid+1,r);
    }
    // 1 2 3 4 4 6 7 7 8 10 12
    // 0 1 2 3 4 5 6 7 8 9 10
    // l                   r
    //           m
}
